\chapter{密码学研究内容}

\section{密码设计}

就是研究如何设计一种满足“安全目标的”密码系统，包括密码设计的方法学和具体的密码设计。按照不同的分类方法，可以分为公钥密码体制(public key cryptosystem)和对称密码体制(secret key cryptosystem / symmetric cryptosystem)。也可以分为流密码（也称序列密码，stream ciphers）和分组密码（block chiphers）等。\par
但是通常在实际应用时，基本的密码算法会在系统的不同实现层次进行应用，并且会用来实现不同的安全目标，而这些也应该是密码应用的研究范畴。\par
在\cite{klein-cry}一书中，其根据密码的应用将密码学分为：
\begin{itemize}
	\item 含糊的安全目标
	\item 形式化的安全目标
	\item 密码协议
	\item 密码学构建模块
	\item 密码学构建模块的实现
\end{itemize}

密码算法设计中的通用要求：
\begin{itemize}
	\item 可逆性(reversible)：这是基本要求，其实就是要求有解密算法的存在。
	\item 对合性(involution)：这是要求加解密算法中的基础计算部分是可以重用的，这样可以使算法实现的工作量减半，这是从实现角度方面考虑的结果。
\end{itemize}

\subsection{密码体制}

一个密码体制是指这样一种数学映射：
\begin{enumerate}
	\item 明文消息空间M，某个字母表上的串集,M表示message。
	\item 密文消息空间C，可能的密文消息集,C表示cipher。
	\item 加密密钥空间$K_e$，可能的加密密钥集，K表示key，e表示encrypt。
	\item 解密密钥空间$K_d$，可能的解密密钥集。d表示decryp。
	\item 加密算法$E:M\times K_e \rightarrow C$,也可写为$c=E_{k_e}(m)$.
	\item 加密算法$D:C\times K_d \rightarrow M$,也可写为$m=D_{k_d}(c)$.
	\item 密码体制满足$D_{k_d}(E_{k_e}(m))=m$.
\end{enumerate}

一个消息的加密密钥和其对应的解密密钥相同时，我们称这种加密方法为对称密码体制，反之称为非对称密码体制。

需要注意的是，自从1976年Michael O. Rabin在“Probabilistic Algorithms”一文中提出概率算法的概念，1984年Shafi Goldwasser和Silvio Micali在“Probabilistic Encryption”加密模型，加密体制中的$E$和$D$可以是概率算法，而不一定确定性函数。

\subsection{基于计算困难问题的密码体制设计}
我们从香农的讨论中知道，我们可以构造一个完全保密(perfect secrecy)密码算法，但是这类密码算法的一个要求就是密钥长度和明文一样长，显然这不具有实操性。那么我们是否能把“数学上的安全”降低为“计算安全”，也就是说，我们并不保证“完全安全”，我们只要保证破解是个需要消耗大量资源的事情即可，比如需要投入100万台计算机，运行100年。也就是说，如果破译者在选择最有效的算法前提以下，破解一个密码体制依然需要很大的资源，而这个资源是破译者无法承受的，那么我们称为这个密码体制是计算安全的。\par
下面是standford大学的Dan Boneh和Voctor Shoup在“A Graduate Course in Applied Cryptography”\cite{boneh-cry} \footnote{此书的电子版下载地址\url{https://toc.cryptobook.us/}}书中的描述：\par

\textbf{2.2 Computational ciphers and semantic security}\par

As we have seen in Shannon's theorem(Theorem 2.5), the only way to achieve perfect security is to have keys that are aslong as messages. However, this is quite impractical: we would like to be able  to encrypt a long message(say, a document of several megabytes) using a short key(say, a few hundred bits). The only way around Shannon's theorem is to relax our security requirements. The way we shall do this is to consider not all possible adversaries, but only computationally feasible adversaries, that is, "real world"adversaries that must perform their calculations on real computers using a reasonable amount of time and memory. This will lead to a weaker definition of security called semantic security. Furthermore, our definition of security will be flexible enough to allow ciphers with variable length message spaces to be considered secure so long as they do not leak any useful information about an encrypted message to an adversary other than the length of message. Also, since our focus is now on the"practical, instead of the"mathematically possible," we shall also insist that the encryption and decryption functions are themselves efficient algorithms, and not just arbitrary functions.\par

计算安全比较通俗的解释是“如果我们使用最好的算法来破译一个密码体制至少需要n次操作，而n是一个非常大的数，则我们称这个密码体制是计算上安全的。”\footnote{\url{http://dict.youdao.com/w/eng/计算安全性/}}。
\footnote{\url{https://wenku.baidu.com/view/25ee2f937dd184254b35eefdc8d376eeafaa17c7.html}}

下面文字来自Denning书“Cryptography and Data Security”\cite{Denning-cry}的1.5.3。\par

\textbf{1.5.3. Ciphers Based on Computationally Hard Problems}\par

In their 1976 paper, Diffie and Hellman \cite{DH-newdirection} suggested applying computional complexity to the design of encryption algorithms. They noted that NP-complete problems might make excellent candidates for ciphers because they cannot be solved in polynomial time by any known techniques. Problems that are computationally more difficult than the problems in NP are not suitable for encryption because the enciphering and deciphering transformations must be fast (i.e. computable in polynomial time). But this means the cryptanalyst could guess a key and check the solution in polynomial time\footnote{多项式时间是指$O(n^k)$，其中k为常数，n为运算的规模，如果对于一个问题能找到一个多项式算法，我们称其为P类问题。} (e. g, by enciphering know plaintext). Thus, the cryptanalytic effort to break any polynomial-time encryption algorithm must be in NP.
\par

Diffie and Hellman speculated that cryptography could draw from the theory of NP complexity by examining ways in which NP-complete problems could be adapted to cryptographic use. Information could be enciphered by encoding it in an NP-complete problem in such a way that breaking the cipher would require solving the problem in the usual way. With the deciphering key, however, a shortcut solution would be possible.
\par

To construct such a cipher, secret "trapdoor" information is inserted into a computationally hard problem that involves inverting a one-way function. A function is a one-way function if it is easy to compute $ f(x) $ for any x in the domain of f, while, for almost all y in the range of f, it is computationally infeasible to compute $f^{-1}(y)$ even if is known. It is a trapdoor one-way function if it is easy to compute $f^{-1}(y)$ given certain additional information. This additional information
is the secret deciphering key.
\par

Public-key systems are based on this principle. The trapdoor knapsack schemes described in Section 2.8 are based on the knapsack problem. The RSA scheme described in Section 2.7 is based on factoring composite numbers.
\par

The strength of such a cipher depends on the computational complexity of the problem on which it is based. A computationally difficult problem does not necessarily imply a strong cryptosystem, however. Shamir gives three reasons\cite{shamir-Cryptocomplexity-knapsack}:\par

1. Complexity theory usually deals with single isolated instances of a problem. A cryptanalyst often has a large collection of statistically related problems to solve(e.g, several ciphertexts generated by the same key).
\par
2. The computational complexity of a problem is typically measured by its worst-case or average-case behavior. To be useful as a cipher, the problem must be hard to solve in almost all cases.
\par
3. An arbitrarily difficult problem cannot necessarily be transformed into a cryptosystem, and it must be possible to insert trapdoor information into the problem in such a way that a shortout solution is possible with this information and only with this information.
\par

Lempel [Lemp79] illustrates the first deficiency with a block cipher for which the problem of finding an n-bit key is NP-complete when the plaintext corresponding to one block of ciphertext is known. But given enough known plaintext, the problem reduces to solving n linear equations in n unknowns. The cipher is described in Section 2.8.4.
\par

Shamir [Sham79] proposes a new complexity measure to deal with the second difficulty, Given a fraction r such that 0 srs I, the percentile complexity $ T(n, r) $ of a problem measures the time to solve the easiest proportion r of the problem instances of size n. For example, T(n, 0.5)gives the median complexity; that is, at least half of the instances of size n can be solved within time $ T(n, 0.5) $. The problem of deciding whether a given integer is prime has median complexity $ O(1) $ because half of the numbers have 2 as a factor, and this can be tested in constant time.
\par

With respect to the third difficulty, Brassard [Bras79b] shows it may not be possible to prove that the cryptanalytic effort to invert a trapdoor one-way function is NP-complete. If the function satisfies a few restrictions, then a proof of NP-completeness would imply \textbf{NP= CoNP}.
\par

\begin{center}
	$\heartsuit \heartsuit \heartsuit \heartsuit \heartsuit \heartsuit \heartsuit \heartsuit \heartsuit$
\end{center}

现代密码理论中的计算安全是基于计算复杂理论(computational complexity)进行讨论的，关于这部分较详细的理论可以参考 Dan Boneh\cite{boneh-cry}和Mao Wenbo\cite{MaoWebBo-ModernCry}的书。计算复杂理论一直是理论计算重要研究内容，并且成为数学研究的一个重要分支，2021年Abel讲就授予了理论计算和离散数学的研究者，相关报道内容见扩展阅读\footnote{2021年3月17日晚，被誉为数学界“诺贝尔奖”的阿贝尔奖揭晓。挪威科学和文学院决定将2021年阿贝尔奖授予匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹(L\'{a}szl\'{o} Lov\'{a}sz)和美国普林斯顿高等研究院教授艾维·维格森(Avi Wigderson)，以“表彰他们在理论计算机科学(theorectical computer science)和离散数学(discrete mathematics)方面作出的杰出贡献，以及使其在现代数学中心领域中发挥主导作用。”}。

\subsection{常见的密码困难假设(Common cryptographic hardness assumptions)}
This is a list of some of the most common cryptographic hardness assumptions, and some cryptographic protocols that use them\footnote{\url{https://encyclopedia.thefreedictionary.com/Computational+hardness+assumption}}.
\begin{itemize}
	\item Integer factorization (整数分解)
	\begin{itemize}
		\item Rabin cryptosystem
		\item Blum Blum Shub generator
		\item Okamoto–Uchiyama cryptosystem
		\item Hofheinz–Kiltz–Shoup cryptosystem
	\end{itemize}
	\item RSA problem (weaker than factorization) 
	\begin{itemize}
		\item RSA cryptosystem
	\end{itemize}
	\item Quadratic residuosity problem (stronger than factorization) (二次剩余问题)
	\begin{itemize}
		\item Goldwasser–Micali cryptosystem
	\end{itemize}
	\item Decisional composite residuosity assumption (stronger than factorization) \footnote{DCRA，是指给定一个合数n和一个整数z，判断z是否是模$n^2$的一个n剩余或是否存在y，满足$z\equiv y^n \pmod{n^2}$}
	\begin{itemize}
		\item Paillier cryptosystem
	\end{itemize}	
	\item Higher residuosity problem (stronger than factorization) 
	\begin{itemize}
		\item Benaloh cryptosystem
		\item Naccache–Stern cryptosystem
	\end{itemize}
	\item Phi-hiding assumption (stronger than factorization) 
	\begin{itemize}
		\item Cachin–Micali–Stadler PIR
	\end{itemize}
	\item Discrete log problem (DLP)(离散对数问题)
	\item Computational Diffie–Hellman assumption (CDH; stronger than DLP) 
	\begin{itemize}
		\item Diffie–Hellman key exchange
	\end{itemize}
	\item Decisional Diffie–Hellman assumption (DDH; stronger than CDH) 
	\begin{itemize}
		\item ElGamal encryption
	\end{itemize}
	\item Shortest Vector Problem (最短向量问题)
	\begin{itemize}
		\item NTRUEncrypt
		\item NTRUSign
	\end{itemize}
\end{itemize}

%\subsection{几种安全定义}
%\footnote{\url{https://crypto.stackexchange.com/questions/70453/what-is-the-relation-between-computational-security-and-provable-security}}



\section{密码分析}

	密码分析（英语：cryptanalysis，来源于希腊语kryptós，即“隐藏”，以及analýein，即“解开”），是一门研究在不知道通常解密所需要的秘密信息的情况下对信息进行解密的学问。通常，这需要寻找一个秘钥。也就是通常我们说的破解密码。\par
	根据密码分析员的能力，可以将密码分析员对密码系统的攻击分为以下几种\cite{qing-cry}：\par
	\begin{enumerate}
		\item 密码分析员掌握除了密钥外，密码系统的加密和解密算法.
		\item 仅知密文攻击(ciphertext-only attack)，密码分析员能够获得密文.
		\item 已知明文攻击(known-plaintext attack)，密码分析员能够获得某些明文和这些明文对应的密文.
		\item 选择明文攻击(chosen-plaintext attack，简写为CPA)，密码分析员能够有选择地获得明文和这些明文对应的密文.
		\item 选择密文攻击(chosen-ciphertext attack，简写为CCA)，密码分析员可以像合法用户那样发送加密的信息.
		\item 密码分析员可以改变、截取或重新发送信息。
	\end{enumerate}	
	
	按照分析的方法，可以分为：\par
	\begin{itemize}
		\item 穷举法，字典攻击。
		\item 数学攻击：统计攻击、差分攻击、线性攻击、代数攻击、相关攻击。
		\item 物理攻击：侧信道分析(side channel attack)和与硬件相关的能量分析、时间分析、声音分析、电磁辐射。通常理论上安全的算法，但由于物理实现上的不足，而使得安全性出现问题，这就对硬件设计、密码芯片设计提出更高要求。
	\end{itemize}
\section{密码测评}
如何评价密码算法的安全性，如何评价好坏，有多好，多坏，以及如何评价一个加密算法在产品实现中的安全性，在系统的实现中都是很重要的。\par
密码测评（cipher evaluation）是与密码分析有着很多相同点，但是又不同的概念，特别是随着密码的产业化应用，这种不同越来越重要，并且相互不能等同。\par
以下是来自论文\cite{cry-evaluate}中对于密码测评和分析概念不同的描述。\par
\emph{Evaluation} is a process intended for highlight some unconformities or deficiencies of a cryptosystem which can be used by a cracker.\par
The evaluation of a cryptographic module can by done using NIST FIPS 140-2 standard (structured on fourth levels) and the evaluation of a product can be done using Common Criteria (ISO 15408)\footnote{此标准在我国对应的是国家标准GB/T18336}, methodology adopted by USA, Canada and EU (structured on seventh levels).\par
\emph{Cracking} represents an operation helping to design a technique, method or algorithm that permit the recovery of the system key or of the plain text having a reduced complexity than brute force attack method:\par
- the evaluator wants to find the minimum quantity of output information that help him to determine, using some strong mathematical tools, a series of information about the cipher algorithm, used key and/or plain text;\par
- the cracker wants to find the maximum quantity of information that help him to deduce the plain text.\par